package dp.pack;

import dp.Common;

import java.util.Arrays;

/**
 * @author : Rookie
 * @description : 01背包
 * @date : 2023/8/15
 */
public class KnapsackProblem {

    public static void main(String[] args) {
        int v = 10;
        int[] weights = new int[] {2, 3, 4, 5};
        int[] values = new int[] {3, 4, 5, 6};
//        System.out.println(getMaxValue(v,weights,values));
        System.out.println(getMaxValue2(v,weights,values));
        System.out.println(solveBy1dArr(v,weights,values));
    }

    private static int solveBy1dArr(int v,int[] weights, int[] values) {
        // dp[j]表示 将物品放入到容量为j的背包中 最大价值为多少
        int[] dp = new int[v + 1];
        for (int i = 0; i < weights.length; i++) {
            for (int j = v; j >= weights[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j-weights[i]] + values[i]);
            }
            System.out.println("i=" + i + "dp数组："+ Arrays.toString(dp));
        }
        Common.print1dArr(dp);
        return dp[v];
    }

    private static int getMaxValue(int v,int []weights,int []values) {
        // dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少
        int[][] dp = new int[weights.length][v + 1];
        // 初始化
        for (int i = weights[0]; i <= v; i++) {
            dp[0][i] = values[0];
        }
        // 遍历物品
        for (int i = 1; i < weights.length; i++) {
            // 遍历背包
            for (int j = 1; j <= v; j++) {
                // 当前物品无法放入背包，继承之前的最优解
                if (j<weights[i]) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    // 选择放入当前物品和不放入当前物品之间的较大值
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weights[i]] + values[i]);
                }
            }
        }
        printArr(dp);
        return dp[weights.length -1][v];
    }

    /**
     * 初始化 dp 数组做了简化(给物品增加冗余维)。这样初始化dp数组，默认全为0即可。
     * dp[i][j] 表示从下标为[0 - i-1]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
     * 其实是模仿背包重量从 0 开始，背包容量 j 为 0 的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为 0。
     * 可选物品也可以从无开始，也就是没有物品可选，即dp[0][j]，这样无论背包容量为多少，背包价值总和一定为 0。
     * @param weights  物品的重量
     * @param values   物品的价值
     * @param v 背包的容量
     */
    private static int getMaxValue2(int v,int []weights,int []values) {
        // dp[i][j] 表示从下标为[0 - i-1]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
        int[][] dp = new int[weights.length+1][v+1];

        for (int i = 1; i <= weights.length; i++) {
            for (int j = 1; j <= v; j++) {
                // i-1对应物品i
                if (j<weights[i-1]) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weights[i-1]] + values[i-1]);
                }
            }
        }

        printArr(dp);
        return dp[weights.length][v];
    }

    private static void printArr(int [][]arr) {
        for (int[] ints : arr) {
            for (int j = 0; j < arr[0].length; j++) {
                System.out.print(ints[j] + " ");
            }
            System.out.println();
        }
    }
}
